package main

import (
	"fmt"
	"go-study/algorithm/common"
	"math"
)

// 如何用 O(1) 的时间复杂度求栈中最小元素

func main() {
	stack := &minStack{
		elementStack:    &common.LinkedStack{Head: &common.LNode{}},
		minElementStack: &common.LinkedStack{Head: &common.LNode{}},
	}
	stack.push(5)
	fmt.Println("栈中的最小值为：", stack.min())
	stack.push(6)
	fmt.Println("栈中的最小值为：", stack.min())
	stack.push(2)
	fmt.Println("栈中的最小值为：", stack.min())
	stack.pop()
	fmt.Println("栈中的最小值为：", stack.min())

}

type minStack struct {
	elementStack    *common.LinkedStack
	minElementStack *common.LinkedStack
}

func (p *minStack) push(data int) {
	p.elementStack.Push(data)
	if p.minElementStack.IsEmpty() || data <= p.minElementStack.Top() {
		p.minElementStack.Push(data)
	}
}

func (p *minStack) pop() int {
	topData := p.elementStack.Pop()
	if topData == p.min() {
		p.minElementStack.Pop()
	}
	return topData
}

func (p *minStack) min() int {
	if p.minElementStack.IsEmpty() {
		return math.MaxInt32
	} else {
		return p.minElementStack.Top()
	}
}
